25 静态单链表的实现

静态单链表的实现

讨论中

A:如果需要频繁增删数据元素，怎么选择线性表？

B:单链表就可以！老师之前在课上讲过。

A:如果数据元素的最大个数固定呢？有没有更好的选择？

B:也许，需要一种新的数据结构...

单链表的一个缺陷
- 触发条件
  - 长时间使用单链表对象频繁增加和删除数据元素
- 可能的结果
  - 堆空间产生大量的内存碎片，导致系统运行缓慢
新的线性表

设计思路:在“单链表”的内部增加一片预留的空间，所有的Node对象都在这片空间中动态创建和动态销毁。
静态单链表的继承层次结构

静态单链表的实现思路
- 通过模板定义静态单链表类(StaticLinkList)
- 在类中定义固定大小的空间(unsigned char[ ])
- 重写create()和destroy()函数，改变内存的分配和归还方式
- 在Node类中重载operator new，用于在指定内存上创建对象

编程实验

静态单链表的实现

#ifndef STATICLINKEDLIST_H
#define STATICLINKEDLIST_H

#include "LinkedList.h"

template<typename T,int N>
class StaticLinkedList:public LinkedList<T>{
    using Node = typename LinkedList<T>::Node;
public:
    int capacity(){
        return N;
    }

protected:
    virtual Node* create(){
        Node *ret = nullptr;
        for(int i=0;i<N;i++){
            if(m_used[i]==false){   //还此空间没使用
                ret = reinterpret_cast<Node*>(m_space)+i;
                ret = new(ret) StaticNode();
                m_used[i] = true;
                break;
            }
        }
        return ret;
    }

    virtual void destroy(Node *node){
        auto begin = reinterpret_cast<StaticNode*>(m_space);
        auto position = reinterpret_cast<StaticNode*>(node);
        for(int i=0;i<N;i++){
            if((begin+i)==position){
                delete position;
                m_used[i] = false;
                break;
            }
        }
    }


private:
    class StaticNode :public Node{
    public:
        void* operator new(size_t ,void *address){
            return address;
        }

        void operator delete(void*){
           // std::cout<<"operator delete(void*)\n";
        }
    };
    unsigned char m_space[N*sizeof (StaticNode)];
    bool m_used[N] = {false};
};

#endif // STATICLINKEDLIST_H

Q&A LinkList中封装create()和destroy()函数的意义是什么？为静态单链表(StaticLinkList)的实现做准备。StaticLinkList与LinkList的不同仅在于链表结点内存分配上的不同；因此，将仅有的不同封装于父类和子类的虚函数中。

小结

顺序表与单链表相结合后衍生出静态单链表
静态单链表是LinkList的子类，拥有单链表的所有操作
静态单链表在预留的空间中创建结点对象
静态单链表适合于频繁增删数据元素的场合(最大元素个数固定)

26 典型问题分析(Bugfix)

典型问题分析(Bugfix)

问题一:创建异常对象时的空指针问题

问题2:LinkList中的数据元素删除
```
LinkList<Test> list;
Test t0(0),t1(1),t2(2);
try {
    list.insert(t0);
    list.insert(t1);    //t1在析构时抛出异常
    list.inser(t2);
    list.remove(1);
} catch(...) {
    cout<<list.length()<<endl;    //???
}
```
问题3 : LinkList中遍历操作与删除操作的混合使用
```
LinkList<int> list;
for(int i=0;i<5;i++) {
    list.insert(i);
}
for(list.move(0);!list.end();list.next()) {
    if(list.current() == 3) {
        //删除成功后，list.current()返回什么值？
        list.remove(list.find(list.current()));
    }
}
```
问题4:StaticLinkList中数据元素删除时的效率问题
```
void destroy(Node *pn) {
    SNode *space = reinterpret_cast<SNode*>(m_space);
    SNode *psn = dynamic_cast<SNode*>(pn);
    for(int i=0;i<N;i++) {
        if(psn==(space+i)) {
            m_used[i] = 0;
            psn->~SNode();     //空间归还，对象析构，即可跳出循环
        }
    }
}
```
问题5:StaticLinkList是否需要提供析构函数
```
int main(){
    StaticLinkList<int,10> sl1;	//如何构造
    for(int i=0;i<10;i++)
        sl1.insert(i);
    return 0;					//如何析构
}
```
类的构造函数和析构函数内部不会发生多态性。所以需要提供构造函数，以正确释放资源。
问题6:DTLib是否有必要增加多维数组类？

多维数组的本质：数组的数组！
实践经验是软件就有bug，因此需要不停的迭代升级，解决问题。库是一种特殊的软件产品，也会存在各种bug,也需要迭代升级，解决问题。

静态单链表的实现​

编程实验​

小结​

26 典型问题分析(Bugfix)

典型问题分析(Bugfix)​

静态单链表的实现

编程实验

小结

典型问题分析(Bugfix)